package librairies.arborescence.arbre;

import librairies.arborescence.interfaces.IBinarbre;

/**
 * binarbre arbre AVL
 * 
 * @author mlozach
 * @param <E> le type de l'elements dans l'arbre.
 */
public class BinarbreAVL<E extends Comparable<E>> extends BinarbreDC<E> 
{
	/**
	 * constructeur par recopie.
	 * @param e la valeur de la racine.
	 */
	public BinarbreAVL(E e) 
	{
		super(e);
	}

	/**
	 * faire une rotation a gauche pour equilibrer.
	 * @return le nouvelle arbre.
	 */
	protected BinarbreDC<E> rotationG() 
	{
		BinarbreDC<E> ancienD = getRight();
		
		if(getRight() != null) 
		{
			setRight(getRight().getLeft());
			
			if(getRight() != null)
			{
				getRight().setFather(this);
			}
			
			ancienD.setRight(getFather());
			
			if(getFather() != null)
			{
				if(getFather().getLeft() == this) 
				{
					getFather().setLeft(ancienD);
				}
				else
				{
					getFather().setRight(ancienD);
				}
			}
			
			ancienD.setLeft(this);
			setFather(ancienD);
			updateHeight();
			
			if(getFather().getFather() != null) 
			{
				getFather().getFather().updateHeight();
			}
			
			return getFather();
		}
		return this;
	}
	
	/**
	 * faire une rotation a droite pour equilibrer.
	 * @return le nouvelle arbre.
	 */
	protected BinarbreDC<E> rotationD() 
	{
		BinarbreDC<E> ancienG = getLeft();
		
		if(getLeft() != null) 
		{
			setLeft(getLeft().getRight());
			
			if(getLeft() != null) 
			{
				getLeft().setFather(this);
			}
			
			ancienG.setFather(getFather());
			
			if(getFather() != null)
			{
				if(getFather().getLeft() == this)
				{
					getFather().setLeft(ancienG);
				}
				else
				{
					getFather().setRight(ancienG);
				}
			}
			
			ancienG.setRight(this);
			setFather(ancienG);
			updateHeight();
			
			if(getFather().getFather() != null)
			{
				getFather().getFather().updateHeight();
			}
			
			return getFather();
		}
		return this;
	}
	
	/**
	 * permet de faire une double rotaion a gauche.
	 * @return le nouvelle arbre.
	 */
	protected BinarbreDC<E> doubleRotationG() 
	{ 
		if(getRight() != null && getRight().getLeft() != null) 
		{
			((BinarbreAVL<?>)getRight()).rotationD();
			return rotationG();
		}
		
		return this;
	}

	/**
	 * permet de faire une double rotaion a droite.
	 * @return le nouvelle arbre.
	 */
	protected BinarbreDC<E> doubleRotationD() 
	{
		if(getLeft() != null && getLeft().getRight() != null) 
		{
			((BinarbreAVL<?>)getLeft()).rotationG();
			return rotationD();
		}
		
		return this;
	}
	
	/**
	 * permet de reequilibre l'arbre entre les niveaux gauche et droite
	 * @return
	 */
	private BinarbreDC<E> reequilibre() 
	{
		BinarbreDC<E> res = this;
		int balance = balance();
		
		if(balance == -2)
		{
			if(getLeft().balance() <= 0)
			{
				res = rotationD();
			}
			else
			{
				res = doubleRotationD();
			}
		}
		
		if(balance==2)
		{
			if(getRight().balance() >= 0)
			{
				res = rotationG();
			}
			else
			{
				res = doubleRotationG();
			}
		}
		
		return res;		
	}

	/**
	 * permet de recree une racine.
	 * @param e la valeur de la racine.
	 * @return la nouvelle racine.
	 */
	protected BinarbreDC<E> buildLeaf(E e)
	{
		return new BinarbreAVL<E>(e);
	}
	
	@Override
	public IBinarbre<E> addVal(E e) 
	{
		IBinarbre<E> res=super.addVal(e);
		
		return ((BinarbreAVL<E>)res).reequilibre();
	}
	
	@Override
	public IBinarbre<E> cutVal(E e) 
	{
		if(e == null)
		{
			return this;
		}
		
		IBinarbre<E> res = super.cutVal(e);
		
		if(res == null)
		{
			return null;
		}
		
		return ((BinarbreAVL<E>)res).reequilibre();
	}
}